//在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
//
//
//
// 示例 1:
//
// 输入: [7,5,6,4]
//输出: 5
//
//
//
// 限制：
//
// 0 <= 数组长度 <= 50000
// Related Topics 树状数组 线段树 数组 二分查找 分治 有序集合 归并排序 👍 693 👎 0

package leetcode.editor.cn;

@SuppressWarnings("all")
//Java：数组中的逆序对
public class 数组中的逆序对 {
    public static void main(String[] args) {
        Solution solution = new 数组中的逆序对().new Solution();
        // TO TEST

        int[] nums = {9,1,0,5,4};
        System.out.println(solution.reversePairs(nums));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int reversePairs(int[] nums) {
            if (nums == null || nums.length <= 1)
                return 0;
            int[] temp = new int[nums.length];
            merge(0, nums.length - 1, nums, temp);
            return count;
        }

        public void merge(int left, int right, int[] nums, int[] temp) {
            if (left < right) {
                int mid = (left + right) / 2;
                merge(left, mid, nums, temp);
                merge(mid + 1, right, nums, temp);
                mergeSort(left, mid, right, nums, temp);
            }
        }


        int count;

        public void mergeSort(int left, int mid, int right, int[] nums, int[] temp) {

            int i = left, j = mid + 1;
            int t = 0;
            while (i <= mid && j <= right) {
                if (nums[i] <= nums[j]) {
                    temp[t++] = nums[i++];
                } else {
                    count += mid - i + 1;
                    temp[t++] = nums[j++];
                }
            }

            while (i <= mid) {
                temp[t++] = nums[i++];
            }

            while (j <= right) {
                temp[t++] = nums[j++];
            }

            t = 0;
            while (left <= right) {
                nums[left++] = temp[t++];
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)


}
